With microprocessor architectures, the number of memory space locations which a particular processor can address is limited by a number of factors. One limiting factor is the number of bits available (typically 16 bits) within the processor's internal registers, where memory space addresses are stored. Since the processor's stack is used for temporary storage of memory space location addresses, the bit-width (typically 16 bits) of the processor's stack is also a limiting factor. Another limiting factor is the width of the processor's Arithmetic Logic Unit ("ALU"), which calculates memory space addresses. Where storage of addresses is to be in 16 bits, the processor has a limited addressable linear memory space of 2**16=256 k locations.
A first prior art attempt to overcome these limiting factors is known as the Harvard Architecture, which employs separate code and data memory spaces, effectively doubling the number of addressable memory locations. This architecture has the disadvantage that it makes inefficient use of memory. Available memory, once allocated to either data or code, can not be reallocated. Furthermore, a particular data structure is limited in size to the amount of memory actually allocated to data, and no more.
A second prior art attempt to overcome the limiting factors makes use of software overlays, where code is stored on a secondary storage device, such as a disk drive, during execution of a program, and pieces of the program code are retrieved, as they are needed, from the secondary storage device into the memory. This method does not extend the linearity of the memory space. An architecture which employs software overlays also has the disadvantage of requiring a secondary storage device. Furthermore, the use of overlays adds significant program execution overhead to both manage the overlays and to retrieve the pieces of program code from the external storage device.
A third prior an attempt to overcome the limiting factors employs memory segmentation. For example, the Intel 8086 microprocessor, manufactured by Intel Corporation of Santa Clara, Calif., employs memory segmentation. The Intel 8086 has 16-bit segment registers which provide base addresses for addressing memory segments. For each memory access, a 20-bit address is calculated by adding the contents of the appropriate segment register, multiplied by 16, to an offset specified in the instruction or in another register. The memory segmentation approach has the disadvantage that it increases both software and hardware complexity. It also has the disadvantage that data structures are limited in size and/or must be located near the beginning of a segment, or additional software complexity is required to traverse segment boundaries.
Furthermore, the use of more than one register, where it is necessary to perform arithmetic on the contents of the registers to form an address, is relatively slow.
A fourth prior art attempt to overcome the limiting factors uses bank switching. In one implementation of bank switching, bits from a microprocessor's output port are used to enable separate memory banks or are decoded as the most significant address bits. A problem with the use of bank switching to overcome memory space limiting factors is that bank switching adds significant hardware and software complexity. The bank switching implementations also limit the size of a particular data structure to the size of a memory bank.